﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class Primes
    {
        public static List<int> getPrimes(int length)
        {
            byte[] array = new byte[length];
            array[0] = 1;
            array[1] = 1;
            for (int i = 2; i < array.Length; i++)
            {
                if (array[i] == 0)
                {
                    for (int j = i + i; j < array.Length; j += i)
                    {
                        array[j] = 1;
                    }
                }

            }
            List<int> primes = new List<int>();
            for (int i = 2; i < array.Length; i++)
            {
                if (array[i] == 0)
                {
                    primes.Add(i);
                }
            }
            return primes;
        }

        public static int GCD(int[] number)
        {
            int a = number[0];
            for (int i = 1; i < number.Length; i++)
            {
                a = GCD(a, number[i]);
            }
            return a;
        }
        
        public static int GCD(int a, int b)
        {
            int tmp;
            if (a < b)
            {
                tmp = a;
                a = b;
                b = tmp;
            }

            while (b > 0)
            {
                tmp = a;
                a = b;
                b = tmp % b;
            }
            return a;
        }
        public static int LCM(int[] number)
        {
            int a = number[0];
            for (int i = 1; i < number.Length; i++)
            {
                a = LCM(a, number[i]);
            }
            return a;
        }
        public static int LCM(int a, int b)
        {
            return a * b / GCD(a, b);
        }
    }
}
